package com.lw.leetcode.arr.c;

import com.lw.test.util.Utils;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 995. K 连续位的最小翻转次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/14 17:37
 */
public class MinKBitFlips {

    public static void main(String[] args) {
        MinKBitFlips test = new MinKBitFlips();

        // 2
//        int[] arr = {0, 1, 0};
//        int k = 1;

        // 3
//        int[] arr = {0, 0, 0, 1, 0, 1, 1, 0};
//        int k = 3;

        // -1
//        int[] arr = {1, 1, 0};
//        int k = 2;

        //
        int[] arr = Utils.getArr(1000, 0, 2);
        int k = 2;

        int i = test.minKBitFlips(arr, k);

        System.out.println(i);
    }


    public int minKBitFlips(int[] nums, int k) {
        int length = nums.length;
        List<Integer> list = new ArrayList<>();
        int count = 0;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            int min = list.size() - 1;
            int max = findMax(list, i);
            boolean flag = ((min - max) & 1) == 0;
            if (min != -1 && list.get(min) < i) {
                flag = true;
            }
            if ((num == 0 && flag) || (num == 1 && !flag)) {
                count++;
                if (i + k > length) {
                    return -1;
                }
                list.add(i + k - 1);
            }
        }
        return count;
    }

    private int findMax(List<Integer> list, int t) {
        if (list.isEmpty()) {
            return -1;
        }
        if (list.get(0) >= t) {
            return -1;
        }
        int st = 0;
        int end = list.size() - 1;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (list.get(m) < t) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }


}
